НОВЫЕ АЛГОРИТМЫ ДЛЯ ВЫЧИСЛЕНИЯ БАЗИСОВ ГРУПП ГОМОЛОГИЙ ДВУМЕРНЫХ ПСЕВДОМНОГООБРАЗИЙ 

Яковлев Евгений Иванович, доктор физико-математических наук, профессор, старший научный сотрудник
лаборатории «Топологические методы в динамике» ВШЭ, Национальный исследовательский университет Высшая
школа экономики (Россия, г. Нижний Новгород, ул. Б. Печерская, 25/12), eyakovlev@hse.ru
Епифанов Владислав Юрьевич, аспирант, Национальный исследовательский Нижегородский государственный университет им. Н. И. Лобачевского (Россия, г. Нижний Новгород, пр. Гагарина, 23), vepifanov92@gmail.com

515.146

DOI

10.21685/2072-3040-2018-2-5

Актуальность и цели. Объекты исследования – двумерные компактные полиэдры с заданным евклидовым клеточным разбиением, являющиеся псевдомногообразиями с краем. Цель – создание новых эффективных алгоритмов для вычисления базисов групп абсолютных и относительных гомологий по модулю 2.
Материалы и методы. Предложена процедура редукции к аналогичной задаче для полиэдров меньшей размерности и содержащих меньшее количество клеток.
Результаты. Разработаны алгоритмы, не использующие матрицы инциденций. Дано их строгое математическое обоснование.
Выводы. Для рассматриваемого класса полиэдров алгоритмы данной работы намного эффективнее стандартных.

Ключевые слова

полиэдр, псевдомногообразие, группа гомологий, алгоритм

 Скачать статью в формате PDF

1. Guskov, I. Topological noise removal / I. Guskov, Z. J. Wood // Graphics Interface Proceedings. – 2001. – P. 19–26.
2. De Silva, V. Homological sensor networks / V. De Silva, R. Glirist // Notices of the American mathematical society. – 2007. – Vol. 54, № 1. – P. 10–17.
3. Базайкин, Я. В. Численный анализ топологических характеристик трехмерных геологических моделей нефтегазовых месторождений / Я. В. Базайкин, В. А. Байков, И. А. Тайманов, А. А. Яковлев // Математическое моделирование. –
2013. – Т. 25, № 10. – С. 19–31.
4. Яковлев, Е. И. Применения топологии в одной численной схеме решения задач механики сплошных сред / Е. И. Яковлев, Д. Т. Чекмарев, В. Ю. Епифанов // Современная геометрия и ее приложения : матер. междунар. конф. (Казань,
27 ноября – 3 декабря 2017 г.). – Казань : КФУ, 2017. – С. 164–168.
5. Зейферт, Г. Топология / Г. Зейферт, В. Трельфалль. – Ижевск : НИЦ РХД, 2001. – 448 с.
6. Cubical singular simplex model for 3D objects and fast computation of homology groups / Chao Jinhui, Nakayama Jyouji // Pattern Recognition, Proceedings of the 13th International Conference on IEEE. – 1996. – Vol. 4. – P. 190–194.
7. Biggs, N. Spanning trees of dual graphs / Norman Biggs // Journal of Combinatorial Theory, Series B. – 1971. – Vol. 11, № 2. – P. 127–131.
8. Яковлев, Е. И. Вычислительная топология / Е. И. Яковлев. – Н. Новгород : Изд-во Нижегород. гос. ун-та, 2005. – 214 с.
9. Ду бровин, Б. А. Современная геометрия. Методы теории гомологий / Б. А. Дубровин, С. П. Новиков, А. Т. Фоменко. – М. : Наука, 1984. – 344 с.
10. Ахо, А. В. Структуры данных и алгоритмы / А. В. Ахо, Д. Э. Хопкрофт, Д. Д. Ульман. – М. : Вильямс, 2001. – 384 с.